package com.cwj.lab3;

import com.cwj.lab1.myArrayList;


/**
 * 最小生成树
 * */
public class Prim {
    class Edge {
        int u, v, val;
//存储结果生成树的边的结点
        public Edge(int u, int v, int val) {
            this.u = u;
            this.v = v;
            this.val = val;
        }

        @Override
        public String toString() {
            return "{" +
                    "u=" + u +
                    ", v=" + v +
                    ", val=" + val +
                    '}';
        }
    }
//用来辅助找边的结点
    class Node {
        int lowCost;
        int close;

        public Node(int lowCost, int close) {
            this.lowCost = lowCost;
            this.close = close;
        }
    }
//寻找最小生成树
    public myArrayList<Edge> getSmallestTree(Graph_matrix graph, int start) {
        //判断图是否有效
        if (graph==null||graph.getV_num() == 0) {
            return null;
        }
        int V_NUM = graph.getV_num();
        Node[] list = new Node[V_NUM];
        list[start] = new Node(0, 0);
        myArrayList<Edge> edgeList = new myArrayList<>();

        //初始化list
        for (int i = 0; i < list.length; i++) {
            if (i == start) continue;
            list[i] = new Node(graph.getVal(start, i), start);
        }
        //每次选取未被选择的（lowCost!=0），但lowCost最小的，作为生成树的边
        for (int i = 0; i < V_NUM - 1; i += 1) {
            int ind = -1, val = Integer.MAX_VALUE;
            for (int j = 0; j < V_NUM; j++) {
                Node tt = list[j];
                if (tt.lowCost != 0 && val > tt.lowCost) {
                    ind = j;
                    val = tt.lowCost;
                }
            }
            //更新确定结点的邻接点的最小距离
            list[ind].lowCost = 0;
            for (int j = 0; j < V_NUM; j++) {
                if (graph.getVal(ind, j) != graph.getINF()) {
                    Node tt=list[j];
                    if (tt.lowCost != 0) {
                        if (tt.lowCost > graph.getVal(ind, j)) {
                            tt.lowCost = graph.getVal(ind, j);
                            tt.close=ind;
                        }
                    }
                }
            }
            //将结点加入结果集
            edgeList.addLast(new Edge(ind, list[ind].close, val));
        }
        return edgeList;
    }

    public void checkEmpty(Graph_matrix graph) {
        if (graph.getV_num() == 0) {
            throw new RuntimeException("图为空");
        }
    }
}
